﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;

namespace Algoritmia.Problems.ShortestPaths.Acyclic
{
    public class RecursiveDagShortestPathsFinder<T> : IMinimumDistanceFinder<T,double>
    {
        private IList<T> _sources;

        #region IMinimumDistanceFinder<T,double>

        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            Func<T, double> D = null;
            D = v =>
                    {
                        double result = (from p in g.Predecessors(v)
                                         select D(p) + d(p, v)).DefaultIfEmpty(double.PositiveInfinity).Min();
                        return Math.Min(_sources.Contains(v) ? 0 : double.PositiveInfinity, result);
                    };
            _sources = sources.ToList();
            return (from v in targets
                    select D(v)).Min();
        }

        #endregion
    }
}
